#include <stdlib.h>
#include <math.h>
#include "heap.h"

#define TAMINICIAL 32
#define ESCALAAGRANDAR 4
#define ESCALAACHICAR 0.5

struct heap_t
{
	void** vector;
	int tam;
	int cant;
	cmp_func_t cmp;
};

void swap(void* vector[], int index_a, int index_b) {

	void* aux = vector[index_a];
	vector[index_a] = vector[index_b];
	vector[index_b] = aux;
}

int indexar_padre(int index_hijo){
	return (index_hijo-1)/2;
}

int indexar_hijo_izq(int index_padre){
	return 2*index_padre + 1;
}


void heapify_up(void** vector, int index_elem, cmp_func_t cmp){

	if (index_elem == 0) return;
	int index_padre = indexar_padre(index_elem);
	void* padre = vector[index_padre];
	void* elem = vector[index_elem];

	int resultado_cmp = cmp(padre, elem);
	if (resultado_cmp < 0){
		swap(vector, index_padre, index_elem);
        	heapify_up(vector, index_padre, cmp);
	}
}

void heapify_down(void** vector, int index_elem, cmp_func_t cmp, int cant){

	int index_hijo_izq = indexar_hijo_izq(index_elem);
	int index_hijo_mayor = index_hijo_izq;		// El hijo mayor es inicialmente el izquierdo
	int index_hijo_der;
	int resultado_cmp;
	while (index_hijo_mayor < cant){ // Mientras el index del hijo este dentro del heap	
		index_hijo_der = index_hijo_izq + 1;   
		if (index_hijo_der < cant){		// Si hay hijo derecho
			resultado_cmp = cmp(vector[index_hijo_der], vector[index_hijo_izq]); // Se compara con el izquierdo
			if (resultado_cmp > 0) index_hijo_mayor++; // Y nos quedamos con el mas grande
		}
		resultado_cmp = cmp(vector[index_elem], vector[index_hijo_mayor]); // Ahora se compara este ultimo con el elemento padre
		if (resultado_cmp > 0)	return; // Si estan en el orden correcto, termina la funcion

		swap(vector, index_elem, index_hijo_mayor); // Sino, se swapean
		index_elem = index_hijo_mayor; // Y se empieza de nuevo el procedimiento desde esta posicion
		index_hijo_izq = indexar_hijo_izq(index_elem);
		index_hijo_mayor = index_hijo_izq;
	}
}

bool heap_redimensionar(heap_t* heap){

	int escala_nuevo_tam;
	if (heap->cant > heap->tam) escala_nuevo_tam = ESCALAAGRANDAR;
	else if (heap->cant < 1/4 * heap->tam && heap->tam > TAMINICIAL) escala_nuevo_tam = ESCALAACHICAR;
	else return true;

	int nuevo_tam = escala_nuevo_tam * heap->tam;
	void** nuevo_vector = realloc(heap->vector, nuevo_tam * sizeof(void*));
	if (nuevo_vector == NULL) return false;

	heap->vector = nuevo_vector;
	heap->tam = nuevo_tam;
	return true;
}


heap_t *heap_crear(cmp_func_t cmp)
{
	heap_t* nuevo_heap = malloc(sizeof(heap_t));
	if (nuevo_heap == NULL) return NULL;
	
	nuevo_heap->vector = malloc(TAMINICIAL * sizeof(void*));
	if (nuevo_heap->vector == NULL){
		free(nuevo_heap);
		return NULL;
	}

	nuevo_heap->tam = TAMINICIAL;
	nuevo_heap->cant = 0;
	nuevo_heap->cmp = cmp;

	return nuevo_heap;
}

bool heap_destruir(heap_t *heap, void destruir_elemento(void *))
{
	if (!heap) return false;
	if (destruir_elemento){
		int i;
		for (i = 0; i < heap->cant; i++){
			destruir_elemento(heap->vector[i]);
		}
	}
	free(heap->vector);
	free(heap);
	return true;
}

size_t heap_cantidad(const heap_t *heap)
{
	if (!heap) return 0;
	return heap->cant; 
}

bool heap_esta_vacio(const heap_t *heap)
{
	if (!heap) return true;	// Se toma la decision arbitraria de considerar a NULL como heap vacio.
	return (heap_cantidad(heap) == 0);
}

bool heap_encolar(heap_t *heap, void *elem)
{
	if (!heap) return false;
	heap->cant++;
	if (!heap_redimensionar(heap)) return false; // Solo se devuelve false en caso de error al redimensionar

	heap->vector[heap->cant - 1] = elem;
	heapify_up(heap->vector, heap->cant - 1, heap->cmp);

	return true;
}

void *heap_ver_max(const heap_t *heap)
{
	if (!heap) return NULL;
	if (heap_esta_vacio(heap)) return NULL;
	return heap->vector[0];
}

void *heap_desencolar(heap_t *heap)
{
	if (!heap) return false;
	if (heap_esta_vacio(heap)) return false;
	heap->cant--;
	
	void* tmp = heap->vector[0];
	heap->vector[0] = heap->vector[heap->cant];
	heapify_down(heap->vector, 0, heap->cmp, heap->cant);
	heap_redimensionar(heap);
	
	return tmp;
}

void heapify(void *elementos[], size_t cant, cmp_func_t cmp)
{
	int i;
	
	for (i = (cant / 2) - 1; i >= 0; i--){
		heapify_down(elementos, i, cmp, cant);	
	}
}
	
void heapsort(void *elementos[], size_t cant, cmp_func_t cmp){
	
	heapify(elementos, cant, cmp); // Se le da la propiedad de heap al vector
	int i;

	for (i = (cant - 1); i > 0; i--){ // Se simula desencolar el maximo del heap
		swap(elementos, 0, i);    // achicando la cantidad a contemplar del vector en cada iteracion, ya que el ultimo elemento
		heapify_down(elementos, 0, cmp, i);	// estara en su lugar correspondiente, al haber sacado el maximo actual del vector.
	}
}

heap_t* heap_clonar(heap_t* heap)
{
	heap_t* clon = heap_crear(heap->cmp);
	if (!clon) return NULL;
	
	clon->cant = heap->cant;
	clon->tam = heap->tam;
	free(clon->vector);
	clon->vector = malloc(clon->tam * sizeof(void*));
	if (!clon->vector){
		free(clon);
		return NULL;
	}
	int i;
	for (i = 0; i < heap->cant; i++)
	{
		clon->vector[i] = heap->vector[i];
	}
	
	return clon;
}
